package algorithm;

public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        boolean hasNext = true;
        ListNode retNode = null;
        ListNode tempNode = null;
        while (hasNext) {
            Integer temp = null;
            int flag = -1;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (lists[i].val < temp || temp == null) {
                    temp = lists[i].val;
                    flag = i;
                }
            }
            if (flag != -1) {
                if (lists[flag].next != null) {
                    lists[flag] = lists[flag].next;
                } else {
                    lists[flag] = null;
                }
            }
            if (temp == null) {
                hasNext = false;
            } else {
                hasNext = true;
                if (retNode == null) {
                    retNode = new ListNode(temp);
                    tempNode = retNode;
                } else {
                    tempNode.next = new ListNode(temp);
                    tempNode = tempNode.next;
                }
            }
        }
        return retNode;
    }

    public static void main(String[] args) {
        MergeKLists mergeKLists = new MergeKLists();
        ListNode n1 = new ListNode(1);
        n1.next = new ListNode(4);
        ListNode n11 = n1.next;
        n11.next = new ListNode(5);

        ListNode n2 = new ListNode(1);
        n2.next = new ListNode(3);
        ListNode n21 = n2.next;
        n21.next = new ListNode(4);

        ListNode n3 = (ListNode) new Object();
//        ListNode n31 = n3.next;
//        n31.next = new ListNode(9);
        ListNode[] listNodes = new ListNode[]{n1, n2, n3};
        mergeKLists.mergeKLists(listNodes);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
